;;; -*- Mode: TEXT -*-

;;; File:  AutoClass:doc;Classes.text
;;;--------------------------------------------------------------------------;;;
;;;  AUTOCLASS 3.0  Released 5/11/90    contact:  Taylor@pluto.arc.nasa.gov  ;;;
;;;  by P. Cheeseman, J. Stutz, R. Hanson, W. Taylor 			     ;;;
;;;  NASA Ames Research Center, MS 244-17, Moffett Field, CA 94035           ;;;
;;;                                                                          ;;;
;;;  Copyright (C) 1990 Research Institute for Advanced Computer Science.    ;;;
;;;  All rights reserved.  The RIACS Software Policy contains specific       ;;;
;;;  terms and conditions on the use of this software, and must be           ;;;
;;;  distributed with any copies.  THIS FILE MAY BE REDISTRIBUTED.  This     ;;;
;;;  copyright and notice must be preserved in all copies made of this file. ;;;
;;;--------------------------------------------------------------------------;;;



    This file discusses what classification is, what a user should expect to
achieve (with AutoClass), and how to use the results.


Why Classification:

    A classification is usually thought of as a partitioning of a set of things
into subsets in which the members are "more similar" to each other than to
non-members.  The concept of "more similar" is open to numerous interpretations.
Whenever we say `this thing is a Fubar' we are assigning the thing to the class
designated by the name 'Fubar'.  Classification is basic to the act of
identification, and provides one of the simplest forms of prediction.  In saying
`all (or most) fubar are snafu' we expect that any thing classified as fubar is
likely to exhibit the property of snafu.  Often the only rational justification
for a statement like `all (or most) fubar are snafu' is a statistical
association or causal hypothesis found by study of the snafu property in things
classified as fubar.


What to classify:

   The members of almost any set of things that can be described in a regular
manner can be classified, however, finding an appropriate representation may be
a problem.  In the AutoClass work we currently limit our analysis to things that
can be described by a set of features or properties, without referring to other
things.  This allows us to represent our things by a data vector corresponding
to a fixed attribute set.  The attributes are names of measurable or
distinguishable properties of the things.  The data values corresponding to each
attribute are thus limited to be either numbers or the elements of a fixed set
of attribute-specific symbols.  AutoClass cannot express relationships between
things because such relationships are not a property of the thing itself.  In
particular, AutoClass cannot express time relationships such as "before" or
"after".  Nor can it account for any sequential ordering of the data.  Despite
these limitations, AutoClass is applicable to the many problems where such
relations do not exist, can be ignored or transformed into appropriate
attributes.  For instance, temporal ordering data can be re-expressed as "time
of (year, week, day)" or "time elapsed since ...".  A similar problem occurs
with `subset' type attributes whose potential values are subsets of a fixed set
of possible values.  These can be transformed into a set of binary attributes
corresponding to each of the possible values.  The number of thing to be
classified can be large or small.  The number of classes AutoClass can be
expected to find is typically much smaller than the number of data.


What is a classification:

    Classification is typically described as a partitioning of the set of
things.  This is the way humans typically approach classification.  Given the
question `what is it?', our response is to say `it is a fubar' or `it is a baz'.
Partitioning is also appealing when we classify in order to predict,
particularly when we want to predict some property of a thing.  However,
partitioning implies sharp boundaries:  either logical subsets of discrete
attributes or subranges of measured attributes.  We may be limited in our
ability to distinguish discrete attribute values, and we are always limited in
our ability to measure continuous attribute values.  Thus a partitioning
classifier may find some things lying "near" the class boundaries for which
unequivocal class assignment is not possible and may not be desirable.

    Our solution to this problem is to redefine what is meant by classification.
In the AutoClass approach, class membership is expressed probabilistically
rather than as logical assignment.  Thus every one of our things is considered
to have a probability that it belongs to each of the possible classes.  These
class membership probabilities must sum to 1 for each thing, because each thing
must belong to **some** class, even though there is insufficient information to
say **which** class.  This form of "fuzzy" classification produces classes that
are closer to everyday concepts of "cats", "cars" and "crazy people" than
partitioning does.  There are no boundaries and no class assignments, only the
membership probabilities.

    When every single thing has a probability of more than .99 in it's most
probable class, the classes are well separated and we have well defined measures
of class similarity and dissimilarity.  If few things have a probability of more
than .5 in any class, it means that the classes are heavily overlapped.  In this
case the combination of the classes into larger structures is usually more
meaningful than considering each class separately.  In either case we have a
measure of how well our classification fits the data and individual data fit the
classes.  No simple partitioning can provide such information.


Class Models:

    We achieve probabilistic classification by redefining the classes in terms
of parameterized probability distributions, such as normal (Gaussian) or beta
distributions.  We choose distributions that mimic the processes that are
suspected of having produced the observed data.  We limit our choice to those
that have a probability value (discrete attributes) or probability density (real
valued attributes) throughout the attribute space.  A thing's class
probabilities are then computed directly from the parameterized class
distributions.  Thus the classes provide statistical models of thing
descriptions.  The class parameters may be thought of as indirectly specifying
regions in attribute space where each class's probability dominates all others.
These regions correspond approximately to the subsets of the attribute space
that a partitioning classifier would use.

   In AutoClass we refer to the functional form of our probability distributions
as the class model.  A **class** is defined as a particular set of parameter
values and their associated model.  A **classification** is defined as a set of
classes and the probabilities of each class.  The classification problem is to
first choose an appropriate class model (or set of alternate models), then to
search out good classifications based on these models, and finally to rate the
relative quality of the alternative classifications.
 
    As an example of such modeling, consider the case of an attribute such as
"height".  If we expect that the measured height of a thing depends only on it's
class, we can model the probable value in terms of a characteristic height.  We
know there will some measurement error and we usually expect to find some
intrinsic variation in the heights of a class of things.  Our model must allow
for such variation.  Also, height is a scalar quantity bounded below by zero.
Experience has shown that such scalar quantities typically have a normal
distribution in Log space (which is not bounded by zero).  Therefore we choose a
log normal distribution for our model.  The corresponding model parameters are
the mean log height and standard deviation of log height.   Given specific
parameter values, we can calculate the probability that any particular
observation would result from measurement of the height of any thing known to be
a member of the class.  Given multiple classes, we can calculate the relative
probability that a particular height would come from each class.

    There is no generally accepted way to rate the relative quality of alternate
classifications.  The method of setting up models and searching out sets of
descriptive classes has been the subject of statistical research for decades.
The type of model that we have described, that gives the probability of the data
conditioned on the hypothesized model and parameters: P(X|H,p); is known as a
likelihood function.  Maximum Likelihood Estimation (MLE) deals with finding the
set of models and parameters that maximizes this probability.  In some quarters
this is the method of choice for classification.  Unfortunately, MLE fails to
provide a convincing way to compare alternate classifications that differ in
class models or the number of classes.  MLE increases with both model complexity
and number of classes (until the class number equals the number of things).
Clearly this contradicts our intuition that moderately simple classifications
are more desirable than very complex ones.
  
    What we would really like to have is the probability of the hypothesized
model given the data, P(H|X).  Alternatively, we can find the **relative**
probabilities of models given the data; i.e.  P(H1|X)/P(H2|X) = P(H1,X)/P(H2,X).
Then we can directly compare alternate models, in this case models with
different numbers of classes.  The value of P(H,X) is obtained from P(H,X) =
P(X|H)P(H), where P(X|H) is obtained by integration over the parameters in
P(X,p|H) = P(X|p,H)P(p|H).  So we need two additional probabilities for each
hypothesized model: the model probability P(H) and the conditional parameter
probability distribution P(p|H).  The mathematics for doing this integration in
the current AutoClass models are described in the appended papers and notes
contained in the file ML-88.tex.


Results from AutoClass

    The result of an AutoClass run is one or more of the best classifications
found.  A classification effecitvly consists of the class model(s) and a set of
classes, each with the class probability and parameters.  Classifications are
rated in terms of the log of the relative marginal probability of the
hypothesized model given the data.  Those with log marginals that differ by less
than 5 are are considered to be nearly equally probable.  This is because any
other model that gives better classifications will probably give far better
classifications.  Note that the log marginal is strongly dependent on the data,
and thus comparisions can only be made between classifications made on a single
database.  


Using Classification results:
 
   The ultimate reason for doing classification is to increase understanding of
the domain or to improve predictions compared to unclassified data.  Given a
classification and a partial observation, one can always use the classification
to make a statistical estimate of the unobserved attribute values.   One can
also use a classification as the departure point for constructing new models, or
theories specific to the particular domain, based on the insight provided by the
classification and the user's domain knowledge.

    When classification is done by partitioning, prediction can only be done by
selecting the classes compatible with a partial observation and then listing the
allowed values or ranges of the unknown attributes.  With statistical
classification, the usual procedure is to select the class that most probably
generates the partial observation and then use that class's distributions for
the unknowns.  This is generally satisfactory only if the probability of the
chosen class is far greater than any other.  The result is quite doubtful when
the thing has relatively high probability of belonging to more than one class,
and especially so when alternative classes predict very different values for the
unknowns.
    
    We prefer to use the class probabilities of the thing to construct a
weighted sum of the predictions of all the classes.  If the resulting attribute
distribution is broad and flat we know that the partial observation does not
contain sufficient relevant information to predict this attribute.  If the
distribution has a sharp single peak we can predict the attribute value with
confidence, knowing that either one class is nearly certain or that a choice
among the most probable classes would be of little influence.  A multiply peaked
distribution gives us a set of weighted choices.  We can still make a
prediction, but now the knowledge of the alternatives and their relative
probabilities may prevent overconfidence.   It is intended to provide facilities
for such prediction in a future release of AutoClass.


Refinement of Statistical Models:

    The models currently used in AutoClass are quite simple.  Basically there
are just the class conditional multinomial model for discrete valued attributes
and the class conditional normal model for continuous valued attributes.  There
are two minor refinements.  For both attribute types we model missing attribute
values as a discrete value of the attribute: `failure to observe'.  This
acknowledges that we are classifying the results of observations, not the things
observed, and must model what we have rather than what we might have obtained.
The second refinement is to allow transformations of continuous valued
attributes.  The simple normal model implicitly assumes that the attribute
values represent noisy measurements of a class point value that could lie
anywhere between plus and minus infinity.  The log normal and log odds normal
transforms extend this to class point values that are bounded below, and bounded
above and below.  Note that all of these are simple class conditional models,
and they assume that the class attribute values are independent.
    
    The simplest way to refine a model is to eliminate consideration of
attributes that are not contributing anything to the classification.  The
obvious case of a discrete attribute where every observation has the same value
is flagged by AutoClass.  A close inspection of the influence value reports will
usually show several attributes that have negligible influence on all classes.
In the absence of strong prior reasons for their retention, these can be
discarded.  One will usually find that this increases the posterior
probabilities and sharpens the probabilities of both the class assignments and
the remaining attributes.  In AutoClass this is done by specifying the `ignore'
model term for any attribute.
    
    The next step is to allow for dependence of attributes within the class.
There are standard ways to do this when using discrete and continuous attributes
separately.  For discrete valued attributes one would use the joint multinomial
model, providing a probability for every possible combination of values for the
multiple attributes.  This has the disadvantage of requiring the estimation of a
great many probability values.  One needs 2^I-1 for I binary attributes and
product(N_i)-1 for I N-arry attributes.  The posterior probability for such a
model is greatly decreased by the very many priors that must be factored in.
Thus one needs a correspondingly large amount of data for this to show an
advantage over the independent multinomial model.  Better results would be
expected from an intermediate course, where the joint model is applied to
independent subsets of the discrete attributes.  But this leads to the problem
of searching for good combinations of the 2^I attribute subsets.  Since the
number of such sets lies between an exponential and factorial this search should
be carefully controlled.  Similarly for real valued attributes that are
correlated within a class, the obvious representation is a covariance matrix in
the standard multi-normal distribution.  As for discrete valued variables, the
number of possible correlations can be very large, and a model that only adds
particular correlation parameters corresponding to significant observed
correlations is essential.  This version of AutoClass assumes independence of
attributes within a class, and does not contain the correlational models
mentioned above.  However, we are actively investigating these extensions, and
expect to implement them in future releases.

    Given that the current version assumes independence of attributes within a
class, what can be done if this is known or suspected not to be true?  One
approach is to apply AutoClass anyway and examine the results--it will still
find the best classification it can under the independence assumption.  Although
these classes are far from optimal, they may still provide insight into the
domain.  A less risky approach is to first do a principle components analysis on
the data set, and to use the new independent variables as input to AutoClass.
This will remove many of the effects of independence assumption.

